package com.kongge.algorithm.demo;

import java.util.ArrayList;
import java.util.List;

/**
 * 输入一个整形数组，数组里有正数也有负数，数组中一个或连续的多个整数组成一个子数组，求所有子数组的和的最大值，要求时间复杂度为O(n)
 * @author gaoshiqi
 *
 */
public class FindGreatestSumOfSubArray implements IAlgorithm {

	public void execute() {
		int[] arr = {1, -2, 3, 10, -4, 7, 2, -5};
		List<Integer> sumMaxList = findGreatestSumOfSubArray(arr);
		if (sumMaxList != null) {
			for (int i = 0; i < sumMaxList.size(); i++) {
				System.out.print(sumMaxList.get(i) + " ");
			}
		}
	}
	
	private List<Integer> findGreatestSumOfSubArray(int[] arr) {
		if (arr == null || arr.length == 0) {
			return null;
		}
		int sum = 0;
		int maxSum = 0;
		List<Integer> sumMaxList = new ArrayList<Integer>();
		List<Integer> sumList = new ArrayList<Integer>();
		for (int i = 0; i < arr.length; i++) {
			int num = arr[i];
			sum += num;
			if (sum < num) {
				sum = num;
				sumList.clear();
			}
			sumList.add(num);
			if (sum > maxSum) {
				maxSum = sum;
				sumMaxList.clear();
				sumMaxList.addAll(sumList);
			}
		}
		return sumMaxList;
	}
	
	
	
}
